1327. Rooks on a chessboard

From the childhood little Garik was interested in a question: in how many ways n rooks can be arranged on the chessboard of size n × n so that they do not hit each other. He was solving this puzzle for a long time for each case, and when he solved the problem – he gave up the chess.

And how fast can you solve this puzzle?

Input. The size of the chessboard n (n ≤ 1000).

Output. Print the answer, found by Garik.

Sample input	Sample output
2	2

SOLUTION

combinatorics

Algorithm analysis

The first rook can be placed on any of the n squares of the first row. The second rook can be placed on any of the n – 1 cells of the second row (it cannot be placed in the column where the first rook is already located). The third rook can be placed on any of the n – 2 squares of the third row and so on. There are n! in total placement of rooks so that they do not attack each other.

Since n ≤ 1000, then to calculate n! long arithmetic must be used.

Algorithm realization

import java.util.*;

import java.math.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

BigInteger res = BigInteger.ONE;

for(int i = 1; i <= n; i++)

res = res.multiply(BigInteger.valueOf(i));

System.out.println(res);

con.close();

}

}